import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 力扣134. 加油站
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int currentGas = 0;
        int startStation = 0;

        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i] - cost[i];
            currentGas += gas[i] - cost[i]; // currentGas = currentGas + gas[i] - cost[i]

            // 如果当前油量不足，从下一个站点重新开始
            // 一但 currentGas 为正了,那么 中间经过的路径 都是无法环绕一周的
            if (currentGas < 0) {
                startStation = i + 1;
                currentGas = 0;
            }
        }

        // 总油量足够才能完成环路
        return totalGas >= 0 ? startStation : -1;
    }
}

// 力扣135. 分发糖果
class Solution1 {
    public int candy(int[] ratings) {
        int res = 0;
        int[] temp = new int[ratings.length];
        Arrays.fill(temp,1);
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                temp[i] = temp[i-1] + 1;
            }
        }
        for(int i = ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                temp[i] = (temp[i]>temp[i+1])?temp[i]:temp[i+1]+1; //注意判断是否temp[i]>temp[i+1]
            }
        }
        for(int i=0;i<ratings.length;i++){
            res += temp[i];
        }
        return res;
    }
}

// 力扣13. 罗马数字转整数
class Solution2{
    public int romanToInt(String s) {
        Map<Character,Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int ans = 0;
        int k = 0;
        while(k<s.length()){
            char c = s.charAt(k);
            int left = map.get(c);
            int right = 0;
            if(k != s.length()-1){
                right = map.get(s.charAt(k+1));
            }
            if(left>=right){
                ans += left;
                k++;
            }else{
                ans += (right - left);
                k+=2;
            }
        }
        return ans;
    }
}